package cuppics;

import org.junit.Test;

public class Prj14 {

	/**
	 * The following iterative sequence is defined for the set of positive
	 * integers:
	 * 
	 * n → n/2 (n is even) n → 3n + 1 (n is odd)
	 * 
	 * Using the rule above and starting with 13, we generate the following
	 * sequence:
	 * 
	 * 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 It can be seen that this
	 * sequence (starting at 13 and finishing at 1) contains 10 terms. Although
	 * it has not been proved yet (Collatz Problem), it is thought that all
	 * starting numbers finish at 1.
	 * 
	 * Which starting number, under one million, produces the longest chain?
	 */
	@Test
	public void test() {

		System.out.println(Calculator.calculate(1000000));

	}

	public static class Calculator {

		public static int calculate(int upLimit) {

			int maxLen = 0;
			int maxId = 3;
			for (int i = 3; i < upLimit; i++) {

				int len = calculateCollatzLen(i);
				if (len > maxLen) {
					maxLen = len;
					maxId = i;
				}

			}
			return maxId;

		}

		public static int calculateCollatzLen(int i) {

			// if (i == 1) {
			// return 1;
			// }
			//
			// if (i % 2 == 0) {
			// return 1 + calculateCollatzLen(i / 2);
			// } else {
			//
			// return 1 + calculateCollatzLen(3 * i + 1);
			// }
			long n = i;
			int count = 1;
			while( n != 1 ){
				if( n % 2 == 0){
					n = n / 2;
				}else{
					n = n * 3 + 1;
				}
				count ++;
			}
			return count;
		}

	}
}
